3.10 Partitions (partition)

1. Definition

An instance of the data type partition consists of a finite set of items (predefined type partition$\_item$) and a partition of this set into blocks.


2. Creation

P

Creates an instance P of type partition and initializes it to the empty partition.


2. Operations

& truecm & truecm & partition_item make_block returns a new partition$\_item$ it and adds the block {it} to partition P.

partition_item find partition_item p returns a canonical item of the block that contains item p, i.e., if P.same_block(p, q) then P.find(p) = P.find(q). p is an item in P.

bool same_block partition_item p, partition_item q returns true if p and q belong to the same block of partition P. p and q are items in P.

void union_blocks partition_item p, partition_item q unites the blocks of partition P containing items p and q. p and q are items in P.


3. Implementation

Partitions are implemented by the union find algorithm with weighted union and path compression (cf. [T83]). Any sequence of n make_block and m≥n other operations takes time O(mα(m, n)).


4. Example

Spanning Tree Algorithms (cf. graph)